//overflow
class Solution {
public:
    const int nxt[4][2]={{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    int m, n;

    void dfs(vector<vector<int>>& heights, vector<vector<bool>> &vis, int x, int y)
    {
        if(vis[x][y]) return; //避重
        vis[x][y]=true;
        for(auto &[dx, dy]:nxt)
        {
            int nx=x+dx, ny=y+dy;
            if(0<=nx&&nx<m&&0<=ny&&ny<n&&heights[nx][ny]>=heights[x][y]) dfs(heights, vis, nx, ny);
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m=heights.size(), n=heights[0].size();
        vector<vector<bool>> PacificVis(m, vector<bool>(n, false));
        vector<vector<bool>> AtlanticVis(m, vector<bool>(n, false));

        for(int j=0; j<n; j++) dfs(heights, PacificVis, 0, j);
        for(int i=0; i<m; i++) dfs(heights, PacificVis, i, 0);

        for(int j=0; j<n; j++) dfs(heights, AtlanticVis, m-1, j);
        for(int i=0; i<m; i++) dfs(heights, AtlanticVis, i, n-1);


        vector<vector<int>> ans;
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(PacificVis[i][j]&&AtlanticVis[i][j]) ans.push_back({i, j});
        return ans;
    }
};